package com.example.algorithm.backtrcaking.backrewrite;

import java.util.*;

/**
 * @author : zhy
 * @since : 2022/8/22
 * 组合数三
 */
public class CombinationSumThree {

    List<List<Integer>> list=new ArrayList<>();
    Deque<Integer> deque=new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        int len=candidates.length;
        boolean []flag=new boolean[len];
        trackBacking(candidates,target,0,0,len,flag);
        return list;
    }

    private void trackBacking(int[] candidates, int target, int startIndex,int sum,int len,boolean []flag) {

        if(sum==target)
        {
            list.add(new ArrayList<>(deque));
            return;
        }

        for(int i=startIndex;i<len&&sum+candidates[i]<=target;i++)
        {
            if(i>0&&candidates[i]==candidates[i-1]&&!flag[i-1])
            {
                continue;
            }
            deque.push(candidates[i]);
            sum+=candidates[i];
            flag[i]=true;
            trackBacking(candidates, target, startIndex+1, sum, len, flag);
            flag[i]=false;
            Integer last = deque.pop();
            sum-=last;
        }
    }


    public static void main(String[] args) {
        CombinationSumThree sumThree = new CombinationSumThree();
        int []can={10,1,2,7,6,1,5};
        List<List<Integer>> listList = sumThree.combinationSum2(can, 8);
        listList.stream().forEach(System.out::println);
    }
}
